# code for prime factors borrowed from here:
# http://pythonism.wordpress.com/2008/05/17/looking-at-factorisation-in-python/
def primefactors(x):
	factorlist=[]
	loop=2
	while loop<=x:
		if x%loop==0:
			x/=loop
			factorlist.append(loop)
		else:
			loop+=1
	return factorlist

# continue to pattern match until the maximum pattern length has been reached
def pattern_match():
	cipher_text = 	'chreevoahmaeratbiaxxw' \
					'tnxbeeophbsbqmqeqerbw' \
					'rvxuoakxaosxxweahbwgj' \
					'mmqmnkgrfvgxwtrzxwiak' \
					'lxfpskautemndcmgtsxmx' \
					'btuiadngmgpsrelxnjelx' \
					'vrvprtulhdnqwtwdtygbp' \
					'hxtfaljhasvbfxngllchr' \
					'zbwelekmsjiknbhwrjgnm' \
					'gjsglxfeyphagnrbieqjt' \
					'amrvlcrremndglxrrimgn' \
					'snrwchrqhaeyevtaqebbi' \
					'peewevkakoewadremxmtb' \
					'hhchrtkdnvrzchrclqohp' \
					'wqaiiwxnrmgwoiifkee'
				
	max_gram = 6
	current_gram = 2
	char_index = 0
	str_factors = ''
	
	while current_gram < max_gram:
		
		# stop looping once end of string is reached
		while char_index < (len(cipher_text) - char_index):
			# gets current pattern to match
			temp_str = cipher_text[char_index:char_index + current_gram]
			# find the pattern repitition if it exists
			position = cipher_text.find(temp_str, char_index + 1)
			# if pattern doesn't repeat, ignore, else print out pattern info
			if position != -1:
				difference = position - char_index
				factors = primefactors(difference)
				for factor in factors:
					str_factors += str(factor) + ','
				output = temp_str + '                ' + str(char_index) + '              ' + str(position) + '         ' + str((difference)) + '             ' + str_factors
				print(output)
				str_factors = ''
			char_index += 1

		char_index = 0
		current_gram += 1

if __name__ == "__main__":
	output = 'Pattern          Start           End       Difference       Prime Factors'
	print(output)
	pattern_match()
	